package com.firmboy.io_collection.algor;

import org.junit.Test;

import java.util.Arrays;
import java.util.Date;
import java.util.Random;

/**
 * 排序算法
 *
 * @author firmboy
 * @create 2018-03-16 下午2:04
 **/
public class Algor {

    private int[] arr = {1,4,6,3,18,3,6,2,99,0,21};

    @Test
    public void test1(){
        //冒泡排序法  时间复杂度为O(n2）
        test1_ext(arr);
        System.out.println(Arrays.toString(arr));
    }


    public void test1_ext(int[] arr){
        for(int i =0 ;i<arr.length;i++){
            for (int j=i+1;j< arr.length;j++){
                if(arr[i]<arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    @Test
    public void test2(){
        //选择排序
        test2_ext(arr);

        System.out.println(Arrays.toString(arr));
    }

    public void test2_ext(int[] arr){
        int index = 0;
        for (int i=0;i<arr.length;i++){
            index = i;
            for (int j=i+1;j<arr.length;j++){
                if(arr[index]>arr[j]){
                    index = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
    }

    @Test
    public void test3(){
        //{1,4,6,3,18,3,6,2,99,0,21}
        //插入排序  是将需要的和前面的排好序的从尾部向前面寻找
        test3_ext(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void test3_ext(int[] arr){

        for (int i=0;i<arr.length-1;i++){
            for (int j=i+1;j>0;j--){
                if(arr[j-1]>arr[j]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
    }

    @Test
    public void test4(){
        //希尔排序
        int len = arr.length/2;
        int zen = arr.length/2;   //这是增量
        for (int i = 0;i<len;i++){

        }


    }

    @Test
    public void test5(){
        //归并排序
        //1.先将数据拆分成一个数据的数组
        //2.然后在两个数据使用合并排序的进行排序
        //3.这个算法比较难懂的地方是用到了一个递归，采用二分法一直将数组拆分到无法拆分

        //int[] arr = {1,4,6,3,18,3,6,2,99,0,21};



    }

    @Test
    public void test5_test(){
        int[] a = {1,3,5,7,9};
        int[] b = {2,4,6,8,10,22,33};
        int[] c = new int[12];

        test5_guibing(a,5,b,7,c);

        System.out.println(Arrays.toString(c));
    }

    @Test
    public void test5_test1(){
        //int[] arr = {1,4,6,3,18,3,6,2,99,0,21};
        long l = System.currentTimeMillis();
        test5_chafen(arr);
        long l1 = System.currentTimeMillis();
        System.out.println("耗时"+(l1-l)+"毫秒");
        System.out.println(Arrays.toString(arr));
    }

    public void test5_chafen(int[] c){
        //int[] arr = {1,4,6,3,18,3,6,2,99,0,21};
        int mid = c.length/2;
        int[] a = new int[mid];
        int[] b = new int[c.length-mid];
        int i=0,j=0;
        while(i<mid){
            a[i] = c[i];
            i++;
        }
        while(j<c.length-mid){
            b[j] = c[mid+j];
            j++;
        }

        if(a.length>1){
            test5_chafen(a);
        }

        if(b.length>1){
            test5_chafen(b);
        }

        test5_guibing(a,a.length,b,b.length,c);

    }

    public void test5_guibing(int[] a,int n,int[] b,int m,int[] c){
        int i=0,j=0,k=0;
        while(i<n && j<m){
            if(a[i]<b[j]){
                c[k++] = a[i++];
            }else{
                c[k++] = b[j++];
            }
        }
        while(i<n){
            c[k++]=a[i++];
        }
        while(j<m){
            c[k++]=b[j++];
        }
    }

    @Test
    public void test6(){
        long l = System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        long l1 = System.currentTimeMillis();
        System.out.println("耗时"+(l1-l)+"毫秒");
        System.out.println(Arrays.toString(arr));


    }

    public void sort(int[] arr,int low,int high){
        int l = low ;
        int h = high;
        int k = low;

        while(l<h){
            while(h>l){
                if(arr[h]<arr[k]){
                    int temp = arr[k];
                    arr[k] = arr[h];
                    arr[h] = temp;
                    k= h;
                    break;
                }
                h--;
            }

            while(l<h){
                if (arr[l]>arr[k]){
                    int temp = arr[k];
                    arr[k] = arr[l];
                    arr[l] = temp;
                    k = l;
                    break;
                }
                l++;
            }
        }

        if (low!=k){
            sort(arr,low,k-1);
        }
        if(high!=k){
            sort(arr,k+1,high);
        }

    }

    @Test
    public void test7(){
        int length = 200000;
        int[] arr = new int[length];

        int i = 0;
        while(i<length){
            arr[i++] = (int)(Math.random()*100);
        }

        //System.out.println(Arrays.toString(arr));
        System.out.println("success");
        long l = 0L;
        long l1 = 0L;

        //冒泡排序
        l = 0L;
        l1 = 0L;
        l = System.currentTimeMillis();
        test1_ext(arr);
        l1 = System.currentTimeMillis();
        System.out.println("冒泡排序耗时"+(l1-l)+"毫秒");

        //选择排序
        l = 0L;
        l1 = 0L;
        l = System.currentTimeMillis();
        test2_ext(arr);
        l1 = System.currentTimeMillis();
        System.out.println("选择排序耗时"+(l1-l)+"毫秒");

        //插入排序
        l = 0L;
        l1 = 0L;
        l = System.currentTimeMillis();
        test3_ext(arr);
        l1 = System.currentTimeMillis();
        System.out.println("插入排序耗时"+(l1-l)+"毫秒");

        //归并排序
        l = 0L;
        l1 = 0L;
        l = System.currentTimeMillis();
        test5_chafen(arr);
        l1 = System.currentTimeMillis();
        System.out.println("归并排序耗时"+(l1-l)+"毫秒");

        //快速排序
        l = 0L;
        l1 = 0L;
        l = System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        l1 = System.currentTimeMillis();
        System.out.println("快速排序耗时"+(l1-l)+"毫秒");

    }

    public void test6_ext(int[] arr){

    }


}
